/**
 * Created With IntelliJ IDEA
 * Description:leetcode：88. 合并两个有序数组
 * <a href="https://leetcode.cn/problems/merge-sorted-array/">...</a>
 * User: DELL
 * Data: 2022-12-04
 * Time: 11:08
 */

//因为这道题要求的是将重新排序好的数组直接放在nums1中，因此
//从后往前遍历更好，若从前往后遍历，则需要一个tmp数组来记录
//排序好的数组，空间复杂度就会很高
public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //排序后的nums1中的数组下标
        int index = m + n - 1;
        //原nums1中的数组下标
        int i = m - 1;
        //nums2中的数组下标
        int j = n - 1;
        //非递减顺序重新排序
        while (i >= 0 && j >= 0) {
            if (nums1[i] <= nums2[j]) {
                nums1[index--] = nums2[j--];
            } else {
                nums1[index--] = nums1[i--];
            }
        }
        //将while遍历nums2中未遍历到的元素直接放入nums1中
        //而若是nums1中有的元素未遍历到，则不需要再进行操作，因为已经在nums1中了
        if (j >= 0) {
            while (j >= 0) {
                nums1[index--] = nums2[j--];
            }
        }
        return;
    }
}
